package leetcode_day._2021._202111;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/11/19 11:37
 * 整数替换
 * 给定一个正整数 n ，你可以做如下操作：
 * 如果 n 是偶数，则用 n / 2替换 n 。如果 n 是奇数，则可以用 n + 1或n - 1替换 n 。
 * n 变为 1 所需的最小替换次数是多少？
 * 算法：贪心 + 位运算
 * 最好的情况是数是 2 的 n 次方，直接除 2 就搞定了
 * 将一个数变成 1 (00..001)2
 * 就是消除 n 各位上的 1
 */
public class _19_397 {

    public int integerReplacement(int _n) {
        long n = _n;
        int ans = 0;
        while (n != 1) {
            if (n % 2 == 0) n /= 2;
            else {
                // 当 n = 3 时，只需要两部
                // 3 -> 4 -> 2 -> 1, 3 -> 2 -> 1
                if (n != 3 && ((n >>> 1 & 1) == 1)) n += 1;
                else n -= 1;
            }
            ++ans;
        }
        return ans;
    }

}
